//
//  Problem162.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/31.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 162. 寻找峰值
 峰值元素是指其值大于左右相邻值的元素。

 给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

 你可以假设 nums[-1] = nums[n] = -∞ 。
  
 示例 1：
     输入：nums = [1,2,3,1]
     输出：2
     解释：3 是峰值元素，你的函数应该返回其索引 2。
 示例 2：
     输入：nums = [1,2,1,3,5,6,4]
     输出：1 或 5
     解释：你的函数可以返回索引 1，其峰值元素为 2；
          或者返回索引 5， 其峰值元素为 6。
 提示：
     1 <= nums.length <= 1000
     -231 <= nums[i] <= 231 - 1
     对于所有有效的 i 都有 nums[i] != nums[i + 1]
 进阶：你可以实现时间复杂度为 O(logN) 的解决方案吗？
 */
@objcMembers class Problem162: NSObject {
    func solution() {
        print(findPeakElement([5,6]))
        print(findPeakElement([5,4]))
        print(findPeakElement([5,4,3]))
        print(findPeakElement([1,4,3]))
        print(findPeakElement([1,2,3]))
        print(findPeakElement([1,2,3,1]))
        print(findPeakElement([1,2,1,3,5,6,4]))
    }
    
    /*
     前提：我们知道有多个峰值，只需要找到一个就行
     峰值：就是 nums[i-1] < nums[i] > nums[i+1]
     那么还是二分法：left = 0，right = len-1, 如果:
     nums[mid] > nums[mid+1], 那么有个峰值肯定 [l, mid]之间 => right = mid
     nums[mid] < nums[mid+1], 那么有个峰值在 [mid+1, r]之间 => left = mid + 1
     */
    func findPeakElement(_ nums: [Int]) -> Int {
        if nums.count == 1 {
            return 0
        }
        var l = 0, r = nums.count-1
        var mid = 0
        while l < r {
            mid = l + (r - l) >> 1
            if nums[mid] > nums[mid+1] {
                r = mid
            } else {
                l = mid + 1
            }
        }
        return r
    }
}
